# 给你一个 n x n 整数矩阵 arr ，请你返回 非零偏移下降路径 数字和的最小值。
#  非零偏移下降路径 定义为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
#
#  示例 1：
# 输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
# 输出：13
# 解释：
# 所有非零偏移下降路径包括：
# [1,5,9], [1,5,7], [1,6,7], [1,6,8],
# [2,4,8], [2,4,9], [2,6,7], [2,6,8],
# [3,4,8], [3,4,9], [3,5,7], [3,5,9]
# 下降路径中数字和最小的是[1,5,7] ，所以答案是13 。
#
#  示例 2：
# 输入：grid = [[7]]
# 输出：7
import heapq
from typing import List


class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        """
        动态规划
        和 LeetCode64类似
        到达(i, j) 必须先到(i - 1, k) 其中 k != j and 0 < k < n
        dp[i][j]表示从起点跳到(i, j)的最小路径和
        则 dp[i][j] = min(dp[i - 1][k]) + grid[i][j] (其中 k != j)
        :param grid:
        :return:
        """
        n = len(grid)
        dp = [grid[0]] + [[0] * n for _ in range(n - 1)]
        for i in range(1, n):
            for j in range(0, n):
                # 通过使用堆进行优化，快速得到上一行中除去dp[i - 1][j]的所有结果
                tmpPreLine = dp[i - 1].copy()
                del tmpPreLine[j]
                heapq.heapify(tmpPreLine)
                dp[i][j] = tmpPreLine[0] + grid[i][j]
        return min(dp[-1])


if __name__ == "__main__":
    grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    print(Solution().minFallingPathSum(grid))
